Bounded Arithmetic, Propositional Logic, and Complexity Theory - 国立公園

Bounded Arithmetic, Propositional Logic, and Complexity Theory

#計算複雑性理論

https://assets.cambridge.org/97805214/52052/cover/9780521452052.jpg

1 Introduction (BAPLaCT)

2 Preliminaries (BAPLaCT)

3 Basic complexity theory (BAPLaCT)

4 Basic propositional logic (BAPLaCT)

5 Basic bounded arithmetic (BAPLaCT)

6 Definability of computations (BAPLaCT)

7 Witnessing theorems (BAPLaCT)

8 Definability and wittnessing in second order theories (BAPLaCT)

9 Translations of arithmetic formulas (BAPLaCT)

10 Finite axiomatizability problem (BAPLaCT)

11 Direct independence proofs (BAPLaCT)

12 Bounds for constant-depth Frege systems (BAPLaCT)

13 Bounds for Frege and extended Frege systems (BAPLaCT)

14 Hard tautologies and optimal proof systems (BAPLaCT)

15 Strength of bounded arithmetic (BAPLaCT)